package com.ai.zuochengyun.phase01.class03;

public class Code08_FastSlowPointer {

    public static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
        public Node next(Node next) {
            this.next = next;
            return this;
        }
    }

    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
     * @param head
     * @return
     */
    public static Node method1(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        Node fast = head;
        Node slow = head;
        // 链表有三个以上节点
        while (fast.next != null && fast.next.next != null) {
            // slow跳一格
            slow = slow.next;
            // fast跳两格
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
     * @param head
     * @return
     */
    public static Node method2(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        // 先往下跳了一格
        Node fast = head.next;
        Node slow = head.next;
        // 链表有三个以上节点
        while (fast.next != null && fast.next.next != null) {
            // slow跳一格
            slow = slow.next;
            // fast跳两格
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
     * @param head
     * @return
     */
    public static Node method3(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        Node fast = head.next;
        Node slow = head;
        // 链表有三个以上节点
        while (fast.next != null && fast.next.next != null) {
            // slow跳一格
            slow = slow.next;
            // fast跳两格
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
     * @param head
     * @return
     */
    public static Node method4(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        Node fast = head.next.next;
        Node slow = head;
        // 链表有三个以上节点
        while (fast.next != null && fast.next.next != null) {
            // slow跳一格
            slow = slow.next;
            // fast跳两格
            fast = fast.next.next;
        }
        return slow;
    }
}
